A switching network typically is made of input ports and output ports that are interconnected by switches and wires, as described in, for example, U.S. Pat. No. 5,521,591 (incorporated by reference herein in its entirety). As described in column 1 lines 17–19 of U.S. Pat. No. 5,521,591, each wire in the network serves as a conduit for transmitting a message from one of its ends to the other of its ends. The term wire (or connection) includes any means for communicating data between switches, such as electrical wires, parallel groups of wires, optical fibers, multiplexed channels over single wires, or free space radio or optical communication paths. A switch (shown in FIG. 1 of U.S. Pat. No. 5,521,591 and attached hereto as FIG. 1) is an atomic unit that resembles a switching network in function (i.e., a switch has input ports 1A and 1B and output ports 1C and 1D, and connects the input ports to the output ports in any desired pattern).
A switching network may route any kind of digital or analog data including voice or video signals. In some networks, the routing is accomplished by setting of switches so that input ports become directly coupled to output ports (e.g., in a telephone network). In other networks, the inputs ports do not become directly coupled to the output ports. Instead, the messages are routed as packets through the network in steps. Typical examples of networks in which switching networks are used include telephone networks, data networks, computer networks, and interconnection networks in parallel data processing systems.
A butterfly network 2 (shown in FIG. 5 of U.S. Pat. No. 5,521,591 and attached hereto as FIG. 2) is a common example of a switching network. Network 2 is referred to as a butterfly network because the connections between nodes form a pattern resembling a butterfly. A butterfly network has the same number of inputs as it has outputs. The inputs are connected to the outputs via a set of switches organized into successive levels of switches. An N-input, N-output butterfly network has log2N+1 (hereinafter log2 will be referred to as lg) levels of switches, each level having N 2×2 switches. Each switch 3 in the butterfly 2 has a distinct reference label <L,r> where L is its level and r is its row. In an N-input butterfly, the level L is an integer between 0 and lgN, and the row r is a lgN-bit binary number. The inputs and outputs reside on levels 0 and lgN, respectively. For L<lgN, a switch labeled <L,r> is connected to switches <L+l,r> and <L+l,r(L)> and, where r(L) denotes r with the Lth bit complemented.
U.S. Pat. No. 5,521,591 also teaches that “a butterfly contains just one path from each input port to each output port” (in column 8, lines 39–42), and suggests a “multibutterfly contains many paths from each input to each output port” (column 8, lines 42–43). Regarding such a multibutterfly, U.S. Pat. No. 5,521,591 states (column 8, lines 43–46) “[i]ndeed, there is still just one logical (up-down) path from any input to any output, but this logical path can be realized as any one of several physical paths.”